◀ Prev · Parts · Full · Next ▶

Let F {\displaystyle F} and F ′ {\displaystyle F'} be the two fragments that need to be combined. There are two ways to do this:cite-ref-ghs-1-4[1]cite-ref-lynch-6-1[6]

• Merge: This operation occurs if both F {\displaystyle F} and F ′ {\displaystyle F'} share a common minimum weight outgoing edge, and L e v e l ( F ) = L e v e l ( F ′ ) {\displaystyle {\mathit {Level}}(F)={\mathit {Level}}(F')} . The level of the combined fragment will be L e v e l ( F ) + 1 {\displaystyle {\mathit {Level}}(F)+1} .

• Absorb: This operation occurs if L e v e l ( F ) < L e v e l ( F ′ ) {\displaystyle {\mathit {Level}}(F)<{\mathit {Level}}(F')} . The combined fragment will have the same level as F ′ {\displaystyle F'} .

Furthermore, when an "Absorb" operation occurs, F {\displaystyle F} must be in the stage of changing the core, while F ′ {\displaystyle F'} can be in an arbitrary stage. Therefore, "Absorb" operations may be done differently depending on the state of F ′ {\displaystyle F'} . Let e {\displaystyle e} be the edge that F {\displaystyle F} and F ′ {\displaystyle F'} want to combine with, and let n {\displaystyle n} and n ′ {\displaystyle n'} be the two nodes connected by e {\displaystyle e} in F {\displaystyle F} and F ′ {\displaystyle F'} , respectively. There are two cases to consider:

◀ Prev · Parts · Full · Next ▶